This invention relates generally to methods and systems for secure information transmission and, more particularly, to securing information communicated between communication devices.
Cryptography is defined as the art and science of preventing eavesdroppers from understanding the meaning of intercepted messages. In such security minded applications, apparently random, as well as truly random number generators, may be used to support the encryption and decryption of information. These number generators are primarily employed to generate “secret keys” for use in cryptographic encoding and decoding of information.
Within the application of a number generator for creating secret keys, a set of secret numbers is used as a cryptographic key for encoding and/or decoding messages. It is important that this key not be known by unauthorized parties, nor discernible via cryptanalysis based on knowledge of messages. A sequence of apparently random numbers, or truly random numbers may be generated to manufacture a plurality of secret keys.
An “apparently random” number is definable as a number within a sequence or progression of successive numbers having a value which is neither practically reconstructible nor may the set of possible values of that particular number be substantially narrowed, even when given (1) copies of the generator algorithms; (2) non-invasive access to the equipment while generating the numbers; and (3) a complete list of all other numbers in the sequence.
Pseudo-random number generators produce a sequence of apparently random numbers utilizing a deterministic algorithm, and assume that any potential unauthorized party has neither access to nor desire to discover the generating algorithm. Pseudo-random numbers serve as an approximation to truly random numbers for a limited set of purposes. Traditional pseudo-random number generators are implemented using linear feedback shift registers or linear congruential generators using either hardware or software. Given the algorithm and current state, such as the contents of a hardware register or values of computer software variables, the output of a pseudo-random number generator may be exactly replicated. As this state information may be inferred from a one or more values within the number sequence, traditional pseudo-random number generators have substantial limitations with respect to cryptography.
Cryptographically secure pseudo-random number generators are special pseudo-random number generators designed to resist attempts to determine the current state of the generated random number sequence through analysis. These systems typically assume that unauthorized parties have complete access to the algorithm, though not to the current state values. Such generators are, however, still deterministic. As such, in the event the current state is breached by cryptoanalysis or other method, all numbers created by the generator in the future—and, in many designs, the past—may be deduced. Typically, in these systems, it is assumed that the legitimate owner of the generator may be trusted not to reveal or exploit knowledge of the current generator state. However, a defecting employee or industrial espionage may compromise a cryptographically secure generator. Thus, these generators also have substantial disadvantages.
Alternatively, a “truly random” sequence of numbers may be defined as one in which there is a theoretical basis for stating that the next number in the sequence cannot be predicted using either a mathematical or scientific method given an arbitrarily long history of the sequence behavior. In particular, a truly random number provides absolutely no pattern, correlation, or dependency among the remaining numbers in a sequence of numbers other than chance patterns. Generating truly random numbers or sequences typically relies on a chaos theory. In chaos theory, chaotically generated numbers are created by repeated experimental trials using a chaotic system with quantized outcomes, such as coin tossing or rolling dice. In a chaotic system, outcomes vary greatly and non-linearly according to minute variations of initial experimental conditions. Therefore, small sources of experimental error that are inevitably present in the physical world are magnified, thereby making it impractical to correlate system outputs, or numbers, with available measurements of system inputs, such as initial conditions. Generating large volumes of chaotic experimental results has in the past, however, required special purpose hardware, such as for example a nonlinear oscillator, which is not readily available. Furthermore, there is no guarantee against unintentionally repeating generated secret key values.
Using deterministic mathematical algorithms that compute simulations of chaotic systems has been proposed as a scheme for generating apparently random numbers. Because such simulations are computed using exactly specified numbers representing initial conditions, the source of apparent randomness due to minute variation of initial conditions is lost when performing simulations instead of physical experiments. These approaches are deterministic and therefore vulnerable and also subject to attack and compromise if the particular chaotic formula being used becomes known or deduced by cryptoanalysis.
Strategies employed in pseudo-random number generator designs have often relied upon specialized digital hardware. One such method uses a linear feedback shift register (“LFSR”) for obtaining an n-bit pseudo random number by serially shifting out bits from the shift register or shift register chain during a substantially long period outside the purview of potential eavesdroppers For example, a sixty four (64) bit maximal length LFSR running at a clocked frequency of 1 MHZ could be sampled every few seconds to approximate a random number sequence. In such an example, the random number sequence will not be repeated for 585,000 years. However, this LFSR approach is still deterministic. As such, all future and past states are predictable when the present state of the shift register is known.